{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sum of Subsequence Widths"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: sumSubseqWidths"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #子序列宽度之和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>一个序列的 <strong>宽度</strong> 定义为该序列中最大元素和最小元素的差值。</p>\n",
    "\n",
    "<p>给你一个整数数组 <code>nums</code> ，返回 <code>nums</code> 的所有非空 <strong>子序列</strong> 的 <strong>宽度之和</strong> 。由于答案可能非常大，请返回对 <code>10<sup>9</sup> + 7</code> <strong>取余</strong> 后的结果。</p>\n",
    "\n",
    "<p><strong>子序列</strong> 定义为从一个数组里删除一些（或者不删除）元素，但不改变剩下元素的顺序得到的数组。例如，<code>[3,6,2,7]</code> 就是数组 <code>[0,3,1,6,2,2,7]</code> 的一个子序列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,1,3]\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>子序列为 [1], [2], [3], [2,1], [2,3], [1,3], [2,1,3] 。\n",
    "相应的宽度是 0, 0, 0, 1, 1, 2, 2 。\n",
    "宽度之和是 6 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2]\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sum-of-subsequence-widths](https://leetcode.cn/problems/sum-of-subsequence-widths/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sum-of-subsequence-widths](https://leetcode.cn/problems/sum-of-subsequence-widths/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,1,3]', '[2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            ans += (pow(2, i, mod) - pow(2, n-i-1, mod)) * x\n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        pre = ans = 0\n",
    "        mul = 1\n",
    "        nums.sort()\n",
    "        for i, num in enumerate(nums):\n",
    "            ans = (ans + num * (mul - 1) - pre) % mod\n",
    "            pre = (pre * 2 + num) % mod\n",
    "            mul  = (mul * 2) % mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i,x in enumerate(nums):\n",
    "            ans += x*(pow(2,i,1000000007) - pow(2,n-1-i,1000000007))\n",
    "            ans %= 1000000007\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            ans += x * (pow(2, i, MOD) - pow(2, n - 1 - i, MOD))\n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "class Solution:\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            ans += (pow(2,i,MOD) - pow(2,n-1-i, MOD))*nums[i]%MOD\n",
    "            \n",
    "        return ans % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        MOD = int(1e9) + 7\n",
    "\n",
    "        nums.sort()\n",
    "\n",
    "        ret = 0\n",
    "        for i in range(n):\n",
    "            ret = (ret + (pow(2, i, MOD) - pow(2, n - 1 - i, MOD)) * nums[i]) % MOD\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        mod = 10** 9+7\n",
    "        for i in range(n):\n",
    "            ans += (pow(2,i,mod)-pow(2,n-1-i,mod)) * nums[i] % mod\n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for i,x in enumerate(nums):\n",
    "            ans += (pow(2,i,MOD) - pow(2,n - 1 - i,MOD))*x\n",
    "            ans %= MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\n",
    "        mod,inv=1000000007,500000004\n",
    "        nums.sort();ans,_0,_1=0,1,pow(2,len(nums)-1,mod)\n",
    "        for i,j in enumerate(nums):ans,_0,_1=(ans+j*(_0-_1)%mod),_0*2%mod,_1*inv%mod\n",
    "        return (ans%mod+mod)%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\n",
    "        nums.sort();n,ans,_2,mod=len(nums),0,1,1000000007\n",
    "        for i in range(1,n):ans,_2=(ans+(nums[i]-nums[0])*_2)%mod,_2*2%mod\n",
    "        x=ans\n",
    "        for i in range(1,n):x=(x-(nums[i]-nums[i-1])*(_2-1)%mod+mod)%mod*500000004%mod;_2=_2*500000004%mod;ans=(ans+x)%mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        mod = 10**9+7\n",
    "        s,res,total = 0,0,0\n",
    "        for i,d in enumerate(nums):\n",
    "            res = (res+total*d%mod-s)%mod\n",
    "            s = (2*s+d)%mod\n",
    "            total = (total*2+1)%mod\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        mod = 10**9+7\n",
    "        s,res,total = 0,0,0\n",
    "        for d in nums:\n",
    "            res = (res+d%mod*total-s)%mod\n",
    "            s = (2*s+d)%mod\n",
    "            total = (total*2+1)%mod\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        mod = 10 ** 9 + 7\n",
    "        n = len(nums)\n",
    "        for i , num in enumerate(nums):\n",
    "            ans += (pow(2,i,mod) - pow(2,n-i-1,mod)) * num\n",
    "            ans %= mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        res = 0\n",
    "        MOD = 10 ** 9 + 7\n",
    "        x, y = nums[0], 2\n",
    "        for j in range(1, len(nums)):\n",
    "            res = (res + nums[j] * (y - 1) - x) % MOD\n",
    "            x = (x * 2 + nums[j]) % MOD\n",
    "            y = y * 2 % MOD\n",
    "        return (res + MOD) % MOD\n",
    "        \n",
    "        # # 子数组的结果\n",
    "        # cnt = 0\n",
    "        # stack = [-1]\n",
    "        # n = len(nums)\n",
    "        # MOD = 10 ** 9 + 7\n",
    "\n",
    "        # nums.append(10 ** 5 + 1)\n",
    "        # for i in range(n):\n",
    "        #     while nums[stack[-1]] <= nums[i]:\n",
    "        #         cur = stack.pop()\n",
    "        #         cnt = (cnt + nums[cur] * (i - cur) * (cur - stack[-1])) % MOD\n",
    "        #     stack.append(i)\n",
    "        # while nums[stack[-1]] < 10 ** 5 + 1:\n",
    "        #     cur = stack.pop()\n",
    "        #     cnt = (cnt + nums[cur] * (n - cur) * (cur - stack[-1])) % MOD\n",
    "    \n",
    "        # nums[-1] = 0\n",
    "        # for i in range(n):\n",
    "        #     while nums[stack[-1]] >= nums[i]:\n",
    "        #         cur = stack.pop()\n",
    "        #         cnt = (cnt - nums[cur] * (i - cur) * (cur - stack[-1]) + MOD) % MOD\n",
    "        #     stack.append(i)\n",
    "        # while nums[stack[-1]] > 0:\n",
    "        #     cur = stack.pop()\n",
    "        #     cnt = (cnt - nums[cur] * (n - cur) * (cur - stack[-1]) + MOD) % MOD\n",
    "        # return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        MOD = 10**9+7\n",
    "\n",
    "        res, prod = 0, 1\n",
    "        for i in range(n):\n",
    "            res = (res + prod * (nums[i]-nums[n-1-i])% MOD)% MOD\n",
    "            prod = (prod*2) % MOD\n",
    "\n",
    "        return res\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "class Solution:\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        \n",
    "        def quickpower(a,k,m):\n",
    "            res = 1\n",
    "            while k:\n",
    "                if k&1:\n",
    "                    res = res * a % m\n",
    "                a = a*a % m\n",
    "                k >>=1\n",
    "            return res % m\n",
    "        \n",
    "        # return sum((pow2[i]-pow2[-1-i])*x for i,x in enumerate(nums))%MOD\n",
    "        return sum((quickpower(2,i,MOD)-quickpower(2,n-1-i,MOD))*x for i,x in enumerate(nums))%MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        res = 0\n",
    "        MOD = 10 ** 9 + 7\n",
    "        x, y = nums[0], 2\n",
    "        for j in range(1, len(nums)):\n",
    "            res = (res + nums[j] * (y - 1) - x) % MOD\n",
    "            x = (x * 2 + nums[j]) % MOD\n",
    "            y = y * 2 % MOD\n",
    "        return (res + MOD) % MOD\n",
    "        \n",
    "        # # 子数组的结果\n",
    "        # cnt = 0\n",
    "        # stack = [-1]\n",
    "        # n = len(nums)\n",
    "        # MOD = 10 ** 9 + 7\n",
    "\n",
    "        # nums.append(10 ** 5 + 1)\n",
    "        # for i in range(n):\n",
    "        #     while nums[stack[-1]] <= nums[i]:\n",
    "        #         cur = stack.pop()\n",
    "        #         cnt = (cnt + nums[cur] * (i - cur) * (cur - stack[-1])) % MOD\n",
    "        #     stack.append(i)\n",
    "        # while nums[stack[-1]] < 10 ** 5 + 1:\n",
    "        #     cur = stack.pop()\n",
    "        #     cnt = (cnt + nums[cur] * (n - cur) * (cur - stack[-1])) % MOD\n",
    "    \n",
    "        # nums[-1] = 0\n",
    "        # for i in range(n):\n",
    "        #     while nums[stack[-1]] >= nums[i]:\n",
    "        #         cur = stack.pop()\n",
    "        #         cnt = (cnt - nums[cur] * (i - cur) * (cur - stack[-1]) + MOD) % MOD\n",
    "        #     stack.append(i)\n",
    "        # while nums[stack[-1]] > 0:\n",
    "        #     cur = stack.pop()\n",
    "        #     cnt = (cnt - nums[cur] * (n - cur) * (cur - stack[-1]) + MOD) % MOD\n",
    "        # return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        ans = 0\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        for i, num in enumerate(nums):\n",
    "            ans = (ans + pow(2, i, mod) * num - pow(2, n - i - 1, mod) * num) % mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        mod = 10**9 + 7\n",
    "        for i in range(n):\n",
    "            ans += (pow(2,i,mod) - pow(2, n-i -1, mod )) * nums[i] % mod\n",
    "        return ans % mod\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        mod = 10**9 + 7\n",
    "        for i in range(n):\n",
    "            ans +=  (pow(2,i,mod) - pow(2,n-1-i,mod)) * nums[i] % mod\n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def quickpow(self, a: int, k: int) -> int:\n",
    "        sum = 1\n",
    "        while k != 0:\n",
    "            if k & 1:\n",
    "                sum = sum * a % (10 ** 9 + 7)\n",
    "            a = a * a % (10 ** 9 + 7)\n",
    "            k //= 2\n",
    "        return sum\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        ans, n = 0, len(nums)\n",
    "        for i in range(n):\n",
    "            ans += (self.quickpow(2, i) - self.quickpow(2, n - 1 - i)) * nums[i]\n",
    "        return ans % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        mod = 10**9+7\n",
    "        s,res = 0,0\n",
    "        for i,d in enumerate(nums):\n",
    "            res = (res+((1<<i)-1)%mod*d-s)%mod\n",
    "            s = (2*s+d)%mod\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "class Solution:\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        # for nums[i], is the max number of  2^i  subsequence.\n",
    "        #               is the min number of 2^(n-1-i) subsequence\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        def quickpower(a,k,m):\n",
    "            res = 1\n",
    "            while k:\n",
    "                if k&1:\n",
    "                    res = res * a % m\n",
    "                a  = a* a % m\n",
    "                k>>=1\n",
    "            return res % m\n",
    "\n",
    "        \n",
    "        for i in range(n):\n",
    "            res+= ((quickpower(2,i, MOD) - quickpower(2,n-i-1,MOD))*nums[i])% MOD\n",
    "        \n",
    "        return res % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        mod = 10**9 + 7\n",
    "        for i in range(n):\n",
    "            ans += (pow(2,i,mod)-pow(2,n-1-i,mod)) * nums[i] % mod \n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        return sum(((1 << k) - (1 << (n - 1 - k))) * nums[k] for k in range(n)) % (10 ** 9 + 7)\n",
    "        \n",
    "        # # 子数组的结果\n",
    "        # cnt = 0\n",
    "        # stack = [-1]\n",
    "        # n = len(nums)\n",
    "        # MOD = 10 ** 9 + 7\n",
    "\n",
    "        # nums.append(10 ** 5 + 1)\n",
    "        # for i in range(n):\n",
    "        #     while nums[stack[-1]] <= nums[i]:\n",
    "        #         cur = stack.pop()\n",
    "        #         cnt = (cnt + nums[cur] * (i - cur) * (cur - stack[-1])) % MOD\n",
    "        #     stack.append(i)\n",
    "        # while nums[stack[-1]] < 10 ** 5 + 1:\n",
    "        #     cur = stack.pop()\n",
    "        #     cnt = (cnt + nums[cur] * (n - cur) * (cur - stack[-1])) % MOD\n",
    "    \n",
    "        # nums[-1] = 0\n",
    "        # for i in range(n):\n",
    "        #     while nums[stack[-1]] >= nums[i]:\n",
    "        #         cur = stack.pop()\n",
    "        #         cnt = (cnt - nums[cur] * (i - cur) * (cur - stack[-1]) + MOD) % MOD\n",
    "        #     stack.append(i)\n",
    "        # while nums[stack[-1]] > 0:\n",
    "        #     cur = stack.pop()\n",
    "        #     cnt = (cnt - nums[cur] * (n - cur) * (cur - stack[-1]) + MOD) % MOD\n",
    "        # return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        mod = 10**9+7\n",
    "        s,res = 0,0\n",
    "        for i,d in enumerate(nums):\n",
    "            res = (res+((1<<i)-1)%mod*d%mod-s)%mod\n",
    "            s = (2*s+d)%mod\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "class Solution:\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        \n",
    "        def quickpower(a,k,m):\n",
    "            res = 1\n",
    "            while k:\n",
    "                if k&1:\n",
    "                    res = res * a % m\n",
    "                a = a*a % m\n",
    "                k >>=1\n",
    "            return res % m\n",
    "        \n",
    "        # return sum((pow2[i]-pow2[-1-i])*x for i,x in enumerate(nums))%MOD\n",
    "        return sum((quickpower(2,i,MOD)-quickpower(2,n-1-i,MOD))*x for i,x in enumerate(nums))%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        mod = 10**9+7\n",
    "        s,res = 0,0\n",
    "        for i,d in enumerate(nums):\n",
    "            res = (res+((1<<i)-1)*d-s)%mod\n",
    "            s = (2*s+d)%mod\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 1:\n",
    "            return 0\n",
    "        mod = int(1e9 + 7)\n",
    "\n",
    "        nums.sort()\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            res += ((1 << i) - (1 << (len(nums) - i - 1))) * nums[i]\n",
    "            res %= mod\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\n",
    "        arr = sorted(nums)\n",
    "        n = len(arr)\n",
    "        k = (n + 1) // 2\n",
    "        mod = 10 ** 9 + 7\n",
    "        ret = 0\n",
    "        for i in range(k):\n",
    "            ret += ((1 << (n - i - 1)) - (1 << i)) * (arr[n-i-1] - arr[i])\n",
    "            ret %= mod\n",
    "        return ret\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "\n",
    "        for i, num in enumerate(nums):\n",
    "            ans = (ans + num * ((1 << i) - (1 << (n - 1 - i)))) % mod\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\n",
    "        nums=sorted(nums)\n",
    "        res=0\n",
    "        power=1\n",
    "        for i in range(len(nums)):\n",
    "            add=power*nums[i]\n",
    "            sub=power*nums[len(nums)-1-i]\n",
    "            res+=(add-sub)\n",
    "            power=(power*2)%(10**9+7)\n",
    "        return res%(10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\n",
    "        arr = sorted(nums)\n",
    "        n = len(arr)\n",
    "        k = (n + 1) // 2\n",
    "        ret = 0\n",
    "        for i in range(k):\n",
    "            ret += ((1 << (n - i - 1)) - (1 << i)) * (arr[n-i-1] - arr[i])\n",
    "            ret %= 10 ** 9 + 7\n",
    "        return ret\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\r\n",
    "class Solution:\r\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\r\n",
    "        nums.sort()\r\n",
    "        Mod=10**9+7\r\n",
    "        n=len(nums)\r\n",
    "        ret=0\r\n",
    "        power=1\r\n",
    "        for i in range(n):\r\n",
    "            add=nums[i]*power\r\n",
    "            sub=nums[n-1-i]*power\r\n",
    "            ret=(ret+add-sub)%Mod\r\n",
    "            power<<=1\r\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\r\n",
    "class Solution:\r\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\r\n",
    "        nums.sort()\r\n",
    "        Mod=10**9+7\r\n",
    "        n=len(nums)\r\n",
    "        ret=0\r\n",
    "        min_cnt=1<<(n-1)\r\n",
    "        max_cnt=1\r\n",
    "        for i in range(n):\r\n",
    "            ret+=nums[i]*(max_cnt-min_cnt)\r\n",
    "            max_cnt*=2\r\n",
    "            min_cnt//=2\r\n",
    "            ret%=Mod\r\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\r\n",
    "class Solution:\r\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\r\n",
    "        nums.sort()\r\n",
    "        Mod=10**9+7\r\n",
    "        n=len(nums)\r\n",
    "        ret=0\r\n",
    "        min_cnt=1<<(n-1)\r\n",
    "        max_cnt=1\r\n",
    "        for i in range(n):\r\n",
    "            ret+=nums[i]*(max_cnt-min_cnt)\r\n",
    "            max_cnt<<=1\r\n",
    "            min_cnt>>=1\r\n",
    "            ret%=Mod\r\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        pow2 = [0 for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            if i == 0: pow2[i] = 1\n",
    "            else: pow2[i] = (pow2[i - 1] + pow2[i - 1]) % mod\n",
    "        for i, x in enumerate(nums):\n",
    "            a = pow2[i]\n",
    "            b = - pow2[n - i - 1]\n",
    "            res = (res + ((a + b) * x) % mod) % mod\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "\n",
    "        mod = (pow(10, 9) + 7)\n",
    "        vpow = []\n",
    "\n",
    "        v = 1\n",
    "        for i in range(len(nums)):\n",
    "            vpow.append(v)\n",
    "            v = v * 2 % mod\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "        r  = 0\n",
    "        for idx, v in enumerate(nums):\n",
    "            r = (r + vpow[idx] * v - vpow[len(nums) - idx - 1] * v) % mod\n",
    "   \n",
    "\n",
    "        return r % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\n",
    "        mod = 10**9+7\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        # pow2 = 1\n",
    "   \n",
    "        # for x , y in zip(nums,reversed(nums)):\n",
    "        #     ans+= (x-y)*pow2\n",
    "        #     pow2=pow2*2 % mod \n",
    "\n",
    "        # return ans % mod\n",
    "        pow2 = [0]*n\n",
    "        pow2[0] = 1\n",
    "        for i in range(1,n):\n",
    "            pow2[i] = pow2[i-1]*2 % mod\n",
    "        \n",
    "        ans =0\n",
    "        for i,x in enumerate(nums):\n",
    "            ans+=x*(pow2[i]-pow2[n-1-i]) % mod\n",
    "        return ans  % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\n",
    "        #  宽度 定义为该序列中最大元素和最小元素的差值\n",
    "        # 所有非空 子序列 的 宽度之和\n",
    "        #  109 + 7 取余\n",
    "        # 子序列 表示可以不连续\n",
    "        # 不都是正数数字，不可以滑动窗口，必须两个数字以上才有值\n",
    "        # 当2为最小值，当2为最大值，不考虑最大值，在遍历前面最小值时，已经取过了\n",
    "        MOD = 10 ** 9 + 7\n",
    "        nums.sort() #排序\n",
    "        n = len(nums)\n",
    "        pow2 = [0] * n\n",
    "        pow2[0] = 1\n",
    "        for i in range(1, n):\n",
    "            pow2[i] = pow2[i - 1] * 2 % MOD  # 预处理 2 的幂次,先求子序列个数\n",
    "        return sum((pow2[i] - pow2[n-1-i]) * x\n",
    "                   for i, x in enumerate(nums)) % MOD\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\n",
    "        #  宽度 定义为该序列中最大元素和最小元素的差值\n",
    "        # 所有非空 子序列 的 宽度之和\n",
    "        #  109 + 7 取余\n",
    "        # 子序列 表示可以不连续\n",
    "        # 不都是正数数字，不可以滑动窗口，必须两个数字以上才有值\n",
    "        # 当2为最小值，当2为最大值，不考虑最大值，在遍历前面最小值时，已经取过了\n",
    "        MOD = 10 ** 9 + 7\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        pow2 = [0] * n\n",
    "        pow2[0] = 1\n",
    "        for i in range(1, n):\n",
    "            pow2[i] = pow2[i - 1] * 2 % MOD  # 预处理 2 的幂次\n",
    "        return sum((pow2[i] - pow2[n-1-i]) * x\n",
    "                   for i, x in enumerate(nums)) % MOD\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 1:\n",
    "            return 0\n",
    "        mod = int(1e9 + 7)\n",
    "\n",
    "        vow = [1] * len(nums)\n",
    "\n",
    "        for i in range(1, len(vow)):\n",
    "            vow[i] = vow[i - 1] * 2 % mod\n",
    "\n",
    "        nums.sort()\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            # res += ((1 << i) - (1 << (len(nums) - i - 1))) * nums[i]\n",
    "            res += (vow[i] - vow[len(nums) - i - 1]) * nums[i]\n",
    "            res %= mod\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        pow2 = [0] * n\n",
    "        pow2[0] = 1\n",
    "        for i in range(1, n):\n",
    "            pow2[i] = pow2[i - 1] * 2 % MOD\n",
    "        res = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            res = (res + (pow2[i] - pow2[n - i - 1]) * num) % MOD\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "            (1) 子序列 ==> 不要求连续，只关心最大/最小\n",
    "            (2) 先排序\n",
    "        \"\"\"\n",
    "        mod = 10**9 + 7\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        pow2 = [0] * n\n",
    "        pow2[0] = 1\n",
    "\n",
    "        for i in range(1, n):\n",
    "            pow2[i] = pow2[i-1] * 2 % mod\n",
    "        return sum((pow2[i] - pow2[-1-i]) * x\n",
    "                   for i, x in enumerate(nums)) % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        total = 0\n",
    "        MOD = int(1e9+7)\n",
    "        pow2 = [0] * n\n",
    "        pow2[0] = 1\n",
    "        for i in range(1,n):\n",
    "            pow2[i] = pow2[i-1]*2 % MOD \n",
    "        return sum((pow2[i]-pow2[n-1-i]) * x \\\n",
    "        for i,x in enumerate(nums))%MOD\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 10**9 + 7\n",
    "class Solution:\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        pow2 = [0] * n\n",
    "        pow2[0] = 1\n",
    "        for i in range(1,n):\n",
    "            pow2[i] =pow2[i-1] * 2 % MOD\n",
    "        return sum((pow2[i]-pow2[-1-i])*x for i,x in enumerate(nums))%MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\n",
    "        \n",
    "        nums = sorted(nums)\n",
    "        n = len(nums)\n",
    "        M = int(1e9) + 7\n",
    "\n",
    "        power = [1]\n",
    "        for _ in range(1, n):\n",
    "            power.append(power[-1] * 2 % M)\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            res = (res + (power[i] - power[n-i-1]) * nums[i]) % M\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\n",
    "        mod,inv=1000000007,500000004\n",
    "        if(len(nums)<7750):nums.sort()\n",
    "        else:\n",
    "            vis=[0]*(max(nums)+1)\n",
    "            for i in nums:vis[i]+=1\n",
    "            nums=[]\n",
    "            for i,j in enumerate(vis):\n",
    "                for k in range(j):nums.append(i)\n",
    "        ans,_0,_1=0,1,pow(2,len(nums)-1,mod)\n",
    "        for i,j in enumerate(nums):ans,_0,_1=(ans+j*(_0-_1)%mod),_0*2%mod,_1*inv%mod\n",
    "        return (ans%mod+mod)%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        p_sum = [0] * n\n",
    "        p_sum[0] = nums[0]\n",
    "        for i in range(1, n):\n",
    "            p_sum[i] = p_sum[i - 1] + nums[i]\n",
    "        sum_widths, temp = 0, 1\n",
    "        mod = 1000000007\n",
    "        for d in range(1, n):\n",
    "            sum1 = p_sum[n - 1] - p_sum[d - 1]\n",
    "            sum2 = p_sum[n - 1 - d]\n",
    "            sum_widths = (sum_widths + (sum1 - sum2) * temp) % mod\n",
    "            temp = (temp * 2) % mod\n",
    "        return sum_widths"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        MOD = 10**9+7\n",
    "        res = 0\n",
    "        if n==1:\n",
    "            return 0\n",
    "        pow_2 = [pow(2,i,MOD) for i in range(n)]\n",
    "\n",
    "        # 先对数组排序\n",
    "        nums.sort()\n",
    "        print(nums)\n",
    "\n",
    "        for i in range(n):\n",
    "            res += (nums[n-1-i]-nums[i])*pow_2[n-1-i]\n",
    "\n",
    "\n",
    "        return res%MOD\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        n = len(nums)\n",
    "        cnt = Counter(nums)\n",
    "        ans = pre = 0\n",
    "        for num in sorted(cnt):\n",
    "            ans += num*(pow(2, cnt[num], mod) - 1)*(pow(2, pre, mod))\n",
    "            pre += cnt[num]\n",
    "            ans %= mod\n",
    "\n",
    "        pre = 0\n",
    "        for num in sorted(cnt, reverse=True):\n",
    "            ans -= num * (pow(2, cnt[num], mod) - 1) * (pow(2, pre, mod))\n",
    "            pre += cnt[num]\n",
    "            ans %= mod\n",
    "        \n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 一.只需要考虑子序列的最大和最小值，所以，这里无关顺序。可以先排序\n",
    "# 二.以下标i的元素作为最大值的子序列个数：\n",
    "# 两种思路：\n",
    "# 1.i左边的元素有两个选择，可选可不选，i位置元素必选，i后面的元素不选\n",
    "# 总个数：2*2*2(i个)*1（i位置）*1*1。。。（i后面的）即，2**i\n",
    "# 2.长度为1：1，长度为2：从i前面的i个数选1个，ci1，长度为3：ci2。。。直到cii。最后结果还是2**i\n",
    "# 三.以下标i的元素作为最小值的子序列个数：\n",
    "# 同样两种思路，与前面相反，现在是考虑i右边的元素\n",
    "# 1.i右边的元素有两个选择，可选可不选，i位置元素必选，i前面的元素不选\n",
    "# 总个数：2*2*2(i后面的n-i-1个数)*1（i位置）*1*1。。。（i前面的）即，2**i\n",
    "# 2.同上\n",
    "class Solution:\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        nums.sort()\n",
    "        MOD=10**9+7\n",
    "        b=[1]*n\n",
    "        s=[1]*n\n",
    "        for i in range(1,n):\n",
    "            b[i]=b[i-1]*2%MOD\n",
    "        for i in range(n-2,-1,-1):\n",
    "            s[i]=s[i+1]*2%MOD\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            ans+=(b[i]-s[i])*nums[i]\n",
    "        return ans%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\n",
    "        mod, ans = 1000000007, 0\n",
    "        cnts = collections.Counter(nums)\n",
    "        vals = [[num, cnts[num]] for num in cnts]\n",
    "        vals.sort()\n",
    "        cur, n = 1, len(vals)\n",
    "        for i in range(n):\n",
    "            cur1 = (cur << vals[i][1]) % mod\n",
    "            tmp = (cur1 - cur) % mod\n",
    "            ans = (ans + tmp * vals[i][0]) % mod\n",
    "            cur = cur1\n",
    "        cur = 1\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            cur1 = (cur << vals[i][1]) % mod\n",
    "            tmp = (cur1 - cur) % mod\n",
    "            ans = (ans - tmp * vals[i][0]) % mod\n",
    "            cur = cur1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sumSubseqWidths(self, nums: List[int]) -> int:\n",
    "        arr=sorted(nums)\n",
    "        sml={}\n",
    "        t=0\n",
    "        for a in arr:\n",
    "            if a not in sml:\n",
    "                sml[a]=t\n",
    "            t+=1\n",
    "        big={}\n",
    "        t=0\n",
    "        while arr:\n",
    "            a=arr.pop()\n",
    "            if a not in big:\n",
    "                big[a]=t\n",
    "            t+=1\n",
    "        mx=mi=0\n",
    "        mod=10**9+7\n",
    "        cnt=Counter(nums)\n",
    "        #print(sml,big,cnt)\n",
    "        for a in cnt.keys():\n",
    "            mx+=a*(pow(2,cnt[a],mod)-1)*pow(2,sml[a],mod)\n",
    "            mx%=mod\n",
    "            mi+=a*(pow(2,cnt[a],mod)-1)*pow(2,big[a],mod)\n",
    "            mi%=mod\n",
    "        return (mx-mi)%mod\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
